MOD = 10 ** 9 + 7


class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        # dp[i] = 下一个匹配i时，方案数
        dp = [0] * (len(s) + 1)
        dp[0] = 1

        for i in range(len(s)):
            if s[i] == "0":
                continue

            j = i + 1
            v = int(s[i])
            while j <= len(s) and v <= k:
                dp[j] = (dp[j] + dp[i]) % MOD
                if j < len(s):
                    v = v * 10 + int(s[j])
                j += 1

        return dp[-1]


if __name__ == "__main__":
    print(Solution().numberOfArrays(s="1000", k=10000))  # 1
    print(Solution().numberOfArrays(s="1000", k=10))  # 0
    print(Solution().numberOfArrays(s="1317", k=2000))  # 8
    print(Solution().numberOfArrays(s="2020", k=30))  # 1
    print(Solution().numberOfArrays(s="1234567890", k=90))  # 34
